#include <iostream>

using namespace std;

/*
Sudoku is a logic-based,[1][2] combinatorial[3] number-placement puzzle. 
The objective is to fill a 9? grid with digits so that each column, each row, 
and each of the nine 3? sub-grids that compose the grid (also called "boxes", 
"blocks", "regions", or "sub-squares") contains all of the digits from 1 to 9. 
The puzzle setter provides a partially completed grid, which typically has a unique solution.

Sodoku introduction: http://en.wikipedia.org/wiki/Sudoku
*/

int GameBoard[9][9]={0};

void InitGame()
{
    GameBoard[0][0] = 5;
    GameBoard[0][1] = 3;
    GameBoard[0][4] = 7;

    GameBoard[1][0] = 6;
    GameBoard[1][3] = 1;
    GameBoard[1][4] = 9;
    GameBoard[1][5] = 5;

    GameBoard[2][1] = 9;
    GameBoard[2][2] = 8;
    GameBoard[2][7] = 6;

    GameBoard[3][0] = 8;
    GameBoard[3][4] = 6;
    GameBoard[3][8] = 3;

    GameBoard[4][0] = 4;
    GameBoard[4][3] = 8;
    GameBoard[4][5] = 3;
    GameBoard[4][8] = 1;

    GameBoard[5][0] = 7;
    GameBoard[5][4] = 2;
    GameBoard[5][8] = 6;

    GameBoard[6][1] = 6;
    GameBoard[6][6] = 2;
    GameBoard[6][7] = 8;

    GameBoard[7][3] = 4;
    GameBoard[7][4] = 1;
    GameBoard[7][5] = 9;
    GameBoard[7][8] = 5;

    GameBoard[8][4] = 8;
    GameBoard[8][7] = 7;
    GameBoard[8][8] = 9;
}

void PrintGameBoard()
{
	for( int i=0; i<9; i++)
	{
		for(int j=0; j<9; j++)
		{
			cout<<GameBoard[i][j]<<" ";
		}
		cout<<endl;
	}
}

bool IsSafe( int x, int y, int value)
{
	if( x<0 || x>=9 || y<0 || y>=9 )
		return false;

	// check the column and row
	for( int i=0; i<9; i++)
	{
		if(GameBoard[x][i] == value || GameBoard[i][y] == value)
			return false;
	}

	// calculate the start position for grid
	int startX = x-x%3;
	int startY = y-y%3;
	for( int i=0; i<3; i++)
	{
		for(int j=0; j<3;j++)
		{
			if( GameBoard[startX+i][startY+j] == value)
				return false;
		}
	}

	return true;
}

//
// (x, y) is the next position to try.
//

bool Solve( int x, int y)
{
	// if y is out of border, re-adjust it to correct position
	if( y == 9 )
	{
		x = x+1;
		y = 0;
	}
	// Reach the end, return
	if(x==9)
		return true;
	// the position is pre-reset, skip it
	if(GameBoard[x][y] != 0 )
	{
		return Solve(x, y+1);
	}

	// try all possible value on current position
	for( int i=1; i<=9; i++)
	{
		if(IsSafe(x, y, i))
		{
			// backtracking
			GameBoard[x][y] = i;
			if( Solve(x, y+1) )
				return true;
			GameBoard[x][y] = 0;
		}
	}
	return false;
}

int main()
{
	InitGame();

	if( Solve(0, 0) )
		PrintGameBoard();

	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}